The conventional way of implementing boolean logic functions consists in interconnecting elementary logic gates thus, combining them to create more complex functions. Only two types of logic gates are required to build any function regardless of the level of complexity needed. For instance, an AND and an INVERTER, or an OR and an INVERTER operators are sufficient and indeed, products known as "Gate Arrays" or GAs which are large arrays of such logic elements, are commercially available to implement specific user functions. Because of the technologies in use and of the way those functions are realized INVERTER and AND (or OR) are always combined to get the simplest possible elementary piece of logic from which everything can be build, for instance, a 2-way NAND gate. This elementary element is replicated many times on the same GA. Hundreds of thousands of said logic elements, or their equivalent, are commonly available on current GAs up to numbers expressed in millions of gates for the largest. Then, it is up to the user to have them interconnected to implement its specific function so as to produce an Application Specific Integrated Circuit or ASIC. This is a long, error prone and often difficult task to carry out even though many software products such as logic-entry tools, logic simulators and synthesizers are available as an aid to the designer. Therefore, all of what is specific in said designs is embedded in the wiring. Implementing complex functions indeed generates a lot of interconnections between the elementary building blocks up to a point where it may be impossible to actually use all of them. A first limitation in the amount of logic which can actually be implemented in a given Gate Array being reached whenever the wiring channels in a particular area are all exhausted thus, preventing further use of the remaining gates. To overcome this problem providers of ASIC solutions like "LSI LOGIC Corporation", a US company with headquarters in California and a worldwide presence, are now offering products with several layers of metal wiring, up to five in the more recent ones, which demand however, that sophisticated and expensive manufacturing facilities and technologies be put in place. Another limitation brought by the wiring is the upper speed at which a particular circuit can be run. As published on the WEB site of the above company at http://www.lsilogic.com an article, posted on February 97, to promote their newest process technology states, under the subtitle "Performance leads the way", that the five metal layers are for shorter signal paths mentioning that `signal interconnections contribute more to performance, or lack of thereof, than gate delays`.
Another approach to implementing logic which is often retained consists in using off-the-shelf Field Programmable Gate Arrays (FPGAs). Those devices are designed in an attempt to overcome the main drawback of the previous approach which resides in the high cost and long delays incurred before being in a position of producing, in quantity, devices tailored to the user application. In FPGAs, all the possible wiring between logic blocks preexist and the customization is achieved by enabling those of the connections between blocks that are necessary to realize the user function. Various means are employed to personalize the wiring e.g. while the circuit is operational, series transistors are permanently turn on, from a background memory in which the circuit customization has been loaded, so establishing paths from block outputs to block inputs and creating the logic function for the particular user application. FPGA logic blocks tend to be more complex than the simpler NAND block, or equivalent, of hard wired GAs, in an attempt to overcome the problem of the wiring complexity between blocks, becoming acute since, in this case, interconnections are not simply formed of pieces of metal but have also to go through devices which must be turn on in one way or another to actually create block interconnections. Incidentally, choosing to have a more complex building block triggers another kind of problems because it is often difficult to exploit a significant portion of the logic potential present in the building block which is wasted. Nevertheless, it remains that a significant part of the FPGAs customization still resides in the wiring between blocks and because all wiring possibilities must preexist on these off-the-shelf non-personalized components a lot of wiring channels and interconnecting devices to create any kind of customization must be available even though they are not going to be used in a particular application. Thus, wiring between blocks is, on FPGAs, an even more important factor which prevents generally from using completely all the logic available on the component. Moreover, paths thus created are most of them going through connecting devices which, although they are intrinsically very fast devices, slow down the upper operating speed of the FPGAs as compared to the equivalent hard wired ASIC previously described solutions based on the same technology, without otherwise expending the logic potential offered on the component. Products of this type are, for instance, offered by the US company "XILINX" with headquarters in California and a world wide representation. On their WEB site, at http://www.xilinx.com, application notes on the subject of wiring and performance such as the following one untitled "XC4000EX Routing: A Comparison with XC4000E and ORCA" published Nov. 17, 1996 (version 1.2) and "Speed Metrics For High-performance FPGAs" published November, 1997 (Application brief XBRF015) clearly testify of the difficulty of achieving a good wiring and of the direct impact of it on performance.
Thus, a major problem when implementing logic is the capability to realize the numerous connections between the generally simple logic blocks available on a standard Gate Array or the more complex ones of FPGAs. In both cases, for a given technology and process, the wiring is the major contributor in limiting the quantity of logic that can actually be used and the speed at which the logic will be able to operate.